<?php
/**
 * User: helloJiu
 * Date: 2021/9/26
 * Time: 14:36
 */

namespace App\Algorithm\DP;


class MaxSubSequence
{
    /**
     * 使用动态规划思想求最大连续子序列
     *
     * @param $nums
     */
    public function getMaxSubSequence($nums){
        // $dp中记录着以i结尾的最大连续子序列和
        // 每个索引结尾的最大连续子序列和只需要和前一个最大子序列和做融合就行, 不用考虑之前的
        $dp = [];
        $dp[0] = $nums[0];
        for ($i=1; $i<count($nums); $i++){
            // 如果+
            if($dp[$i-1] + $nums[$i] > $nums[$i]){
                $dp[$i] = $dp[$i-1] + $nums[$i];
            }else{
                $dp[$i] = $nums[$i];
            }
        }
        return max($dp);
    }
}